Hacker's Secrets 4/Hacker's Secrets 4.iso/misc/password.txt

Text File | 1991-06-30 | 22KB | 596 lines

        Password Security: A Case History Encryption
                         Computing


                       Robert Morris

                        Ken Thompson




                          ABSTRACT

          This  paper  describes  the  history  of  the
     design  of  the  password  security  scheme  on  a
     remotely  accessed   time-sharing   system.    The
     present   design  was  the  result  of  countering
     observed attempts to penetrate  the  system.   The
     result  is  a  compromise between extreme security
     and ease of use.



April 3, 1978



        Password Security: A Case History Encryption
                         Computing


                       Robert Morris

                        Ken Thompson




                        INTRODUCTION

     Password security on the UNIX time-sharing system  [1]
is  provided by a collection of programs whose elaborate and
strange design is the outgrowth of many years of  experience
with  earlier versions.  To help develop a secure system, we
have had a continuing competition  to  devise  new  ways  to
attack  the security of the system (the bad guy) and, at the
same time, to  devise  new  techniques  to  resist  the  new
attacks  (the  good  guy).  This competition has been in the
same vein  as  the  competition  of  long  standing  between
manufacturers  of  armor  plate  and those of armor-piercing
shells.  For this reason, the description that follows  will
trace  the history of the password system rather than simply
presenting the program in its current state.  In  this  way,
the  reasons  for  the  design  will be made clearer, as the
design cannot be understood without also  understanding  the
potential attacks.

     An underlying goal has been to provide  password  secu-
rity  at  minimal  inconvenience to the users of the system.
For example, those who want to run a completely open  system
without  passwords,  or to have passwords only at the option
of the individual users, are able to do so, while those  who
require  all  of  their  users to have passwords gain a high
degree of security against  penetration  of  the  system  by
unauthorized users.

     The password system must be able not  only  to  prevent
any access to the system by unauthorized users (i.e. prevent
them from logging in at all), but it must also prevent users
who  are  already  logged in from doing things that they are
not authorized to do.  The so  called  ``super-user''  pass-
word,  for  example,  is  especially  critical  because  the
super-user has all sorts of permissions and has  essentially
unlimited access to all system resources.

_________________________
|- UNIX is a trademark of Bell Laboratories.










                           - 2 -


     Password security is of course only  one  component  of
overall  system  security, but it is an essential component.
Experience has shown  that  attempts  to  penetrate  remote-
access systems have been astonishingly sophisticated.

     Remote-access  systems  are  peculiarly  vulnerable  to
penetration  by outsiders as there are threats at the remote
terminal, along the communications link, as well as  at  the
computer  itself.   Although  the  security  of  a  password
encryption algorithm  is  an  interesting  intellectual  and
mathematical  problem,  it  is only one tiny facet of a very
large problem.  In practice, physical security of  the  com-
puter,  communications  security of the communications link,
and physical control of the computer itself loom as far more
important  issues.  Perhaps most important of all is control
over the actions of ex-employees, since they are  not  under
any  direct  control  and  they  may have intimate knowledge
about the system, its  resources,  and  methods  of  access.
Good  system  security  involves realistic evaluation of the
risks not only of deliberate  attacks  but  also  of  casual
unauthorized access and accidental disclosure.

PROLOGUE

     The UNIX system was first implemented with  a  password
file  that  contained the actual passwords of all the users,
and for that reason the password file had to be heavily pro-
tected  against being either read or written.  Although his-
torically, this had been  the  technique  used  for  remote-
access systems, it was completely unsatisfactory for several
reasons.

     The technique is excessively vulnerable  to  lapses  in
security.   Temporary  loss of protection can occur when the
password file is being edited or otherwise modified.   There
is  no  way  to  prevent  the making of copies by privileged
users.  Experience with several earlier  remote-access  sys-
tems  showed  that  such  lapses occur with frightening fre-
quency.  Perhaps the most memorable such  occasion  occurred
in  the  early  60's when a system administrator on the CTSS
system at MIT was editing the password file and another sys-
tem  administrator  was  editing  the  daily message that is
printed on everyone's terminal on login.  Due to a  software
design  error,  the  temporary editor files of the two users
were interchanged and thus, for a time,  the  password  file
was printed on every terminal when it was logged in.

     Once such a lapse  in  security  has  been  discovered,
everyone's password must be changed, usually simultaneously,
at a considerable administrative cost.  This is not a  great
matter, but far more serious is the high probability of such
lapses going unnoticed by the system administrators.

     Security  against  unauthorized   disclosure   of   the









                           - 3 -


passwords  was,  in  the last analysis, impossible with this
system because, for example, if the  contents  of  the  file
system  are put on to magnetic tape for backup, as they must
be, then anyone who has physical access to the tape can read
anything on it with no restriction.

     Many programs must get  information  of  various  kinds
about the users of the system, and these programs in general
should have no special permission to read the password file.
The  information which should have been in the password file
actually was distributed (or replicated) into  a  number  of
files,  all  of  which had to be updated whenever a user was
added to or dropped from the system.

THE FIRST SCHEME

     The obvious solution is to arrange that  the  passwords
not  appear in the system at all, and it is not difficult to
decide that this can be done by encrypting each user's pass-
word,  putting only the encrypted form in the password file,
and throwing away his original password  (the  one  that  he
typed  in).  When the user later tries to log in to the sys-
tem, the password that he types is  encrypted  and  compared
with the encrypted version in the password file.  If the two
match, his login attempt is accepted.   Such  a  scheme  was
first  described  in [3, p.91ff.].  It also seemed advisable
to devise a system in which neither the  password  file  nor
the  password  program itself needed to be protected against
being read by anyone.

     All that was needed to implement  these  ideas  was  to
find  a  means  of  encryption  that  was  very difficult to
invert, even when the encryption program is available.  Most
of  the  standard  encryption methods used (in the past) for
encryption of messages are rather easy to  invert.   A  con-
venient and rather good encryption program happened to exist
on the system at the time; it  simulated  the  M-209  cipher
machine  [4]  used by the U.S. Army during World War II.  It
turned out that the M-209 program was  usable,  but  with  a
given  key, the ciphers produced by this program are trivial
to invert.  It is a much more difficult matter to  find  out
the  key given the cleartext input and the enciphered output
of the program.  Therefore, the password was used not as the
text  to  be  encrypted  but  as the key, and a constant was
encrypted using this key.  The encrypted result was  entered
into the password file.

ATTACKS ON THE FIRST APPROACH

     Suppose that the bad guy has available the text of  the
password  encryption program and the complete password file.
Suppose also that he has substantial computing  capacity  at
his disposal.










                           - 4 -


     One  obvious  approach  to  penetrating  the   password
mechanism  is to attempt to find a general method of invert-
ing the encryption algorithm.  Very  possibly  this  can  be
done, but few successful results have come to light, despite
substantial efforts extending over a  period  of  more  than
five  years.   The results have not proved to be very useful
in penetrating systems.

     Another approach to penetration is simply to keep  try-
ing  potential  passwords until one succeeds; this is a gen-
eral cryptanalytic approach called key search.  Human beings
being  what  they are, there is a strong tendency for people
to choose relatively short and simple  passwords  that  they
can  remember.   Given  free choice, most people will choose
their passwords from a restricted character  set  (e.g.  all
lower-case  letters),  and will often choose words or names.
This human habit makes the  key  search  job  a  great  deal
easier.

     The critical factor  involved  in  key  search  is  the
amount of time needed to encrypt a potential password and to
check the result against an entry in the password file.  The
running  time  to  encrypt  one trial password and check the
result turned out to be approximately 1.25 milliseconds on a
PDP-11/70 when the encryption algorithm was recoded for max-
imum speed.  It is takes essentially no more  time  to  test
the encrypted trial password against all the passwords in an
entire password file, or for that matter, against  any  col-
lection  of encrypted passwords, perhaps collected from many
installations.

     If we want to check all passwords of length n that con-
sist  entirely  of  lower-case  letters,  the number of such
passwords is $26 sup n$.  If we suppose  that  the  password
consists  of  printable  characters only, then the number of
possible passwords is somewhat less than $95 sup  n$.   (The
standard  system ``character erase'' and ``line kill'' char-
acters are, for  example,  not  prime  candidates.)  We  can
immediately estimate the running time of a program that will
test every password of a given length with all of its  char-
acters  chosen  from  some set of characters.  The following
table gives estimates of the  running  time  required  on  a
PDP-11/70  to  test all possible character strings of length
$n$ chosen from various  sets  of  characters:  namely,  all
lower-case  letters, all lower-case letters plus digits, all
alphanumeric characters, all 95 printable ASCII  characters,
and finally all 128 ASCII characters.



                           - 5 -


One has to conclude that it is no great matter  for  someone
with  access  to  a PDP-11 to test all lower-case alphabetic
strings up to length five and, given access to  the  machine
for,  say,  several weekends, to test all such strings up to
six characters in length.  By using such a program against a
collection  of  actual  encrypted  passwords,  a substantial
fraction of all the passwords will be found.

     Another profitable approach for the bad guy is  to  use
the  word  list from a dictionary or to use a list of names.
For example, a large commercial  dictionary  contains  typi-
callly  about  250,000  words; these words can be checked in
about five minutes.  Again, a  noticeable  fraction  of  any
collection  of  passwords  will  be found.  Improvements and
extensions will be (and have been) found by a determined bad
guy.  Some ``good'' things to try are:

-    The dictionary with the words spelled backwards.

-    A list of first names (best obtained from some  mailing
     list).   Last  names, street names, and city names also
     work well.

-    The above with initial upper-case letters.

-    All valid license plate numbers in your  state.   (This
     takes about five hours in New Jersey.)

-    Room  numbers,  social  security   numbers,   telephone
     numbers, and the like.

     The authors have conducted experiments to try to deter-
mine  typical  users' habits in the choice of passwords when
no constraint is put on  their  choice.   The  results  were
disappointing,  except  to  the bad guy.  In a collection of
3,289 passwords gathered from many users over a long  period
of time;

     15 were a single ASCII character;

     72 were strings of two ASCII characters;

     464 were strings of three ASCII characters;

     477 were string of four alphamerics;

     706 were five letters, all  upper-case  or  all  lower-
     case;










                           - 6 -


     605 were six letters, all lower-case.

An additional 492 passwords appeared  in  various  available
dictionaries,  name  lists, and the like.  A total of 2,831,
or 86% of this sample of passwords fell into  one  of  these
classes.

     There was, of course, considerable overlap between  the
dictionary  results  and the character string searches.  The
dictionary search alone, which required only five minutes to
run, produced about one third of the passwords.

     Users could be urged (or forced) to use  either  longer
passwords  or  passwords chosen from a larger character set,
or the system could itself choose passwords for the users.

AN ANECDOTE

     An entertaining and instructive example is the  attempt
made at one installation to force users to use less predict-
able passwords.  The users did not choose  their  own  pass-
words;  the  system  supplied  them.  The supplied passwords
were eight characters long and were taken from the character
set  consisting of lower-case letters and digits.  They were
generated by a pseudo-random number generator with  only  $2
sup 15$ starting values.  The time required to search (again
on a PDP-11/70) through all character strings  of  length  8
from a 36-character alphabet is 112 years.

     Unfortunately, only $2 sup 15$ of them need  be  looked
at,  because  that  is the number of possible outputs of the
random number generator.  The bad guy did, in fact, generate
and  test  each  of these strings and found every one of the
system-generated passwords using a total of only  about  one
minute of machine time.

IMPROVEMENTS TO THE FIRST APPROACH

1.  Slower Encryption

     Obviously, the first algorithm used was far  too  fast.
The  announcement of the DES encryption algorithm [2] by the
National Bureau of Standards was timely and fortunate.   The
DES  is,  by design, hard to invert, but equally valuable is
the fact that it  is  extremely  slow  when  implemented  in
software.  The DES was implemented and used in the following
way: The first eight characters of the user's  password  are
used  as  a  key  for the DES; then the algorithm is used to
encrypt a constant.  Although this constant is zero  at  the
moment,   it   is   easily   accessible   and  can  be  made
installation-dependent.  Then the DES algorithm is  iterated
25  times and the resulting 64 bits are repacked to become a
string of 11 printable characters.










                           - 7 -


2.  Less Predictable Passwords

     The password entry program was modified so as  to  urge
the  user to use more obscure passwords.  If the user enters
an alphabetic password (all upper-case  or  all  lower-case)
shorter  than  six  characters,  or a password from a larger
character set shorter than five characters, then the program
asks  him  to enter a longer password.  This further reduces
the efficacy of key search.

     These improvements make  it  exceedingly  difficult  to
find  any  individual  password.   The user is warned of the
risks and if he cooperates, he is very safe indeed.  On  the
other hand, he is not prevented from using his spouse's name
if he wants to.

3.  Salted Passwords

     The key search technique is still likely to turn  up  a
few passwords when it is used on a large collection of pass-
words, and it seemed wise to make this task as difficult  as
possible.   To  this  end, when a password is first entered,
the password program obtains  a  12-bit  random  number  (by
reading  the  real-time clock) and appends this to the pass-
word typed in by  the  user.   The  concatenated  string  is
encrypted  and  both  the 12-bit random quantity (called the
$salt$) and the 64-bit result of the encryption are  entered
into the password file.

     When the user later logs in to the system,  the  12-bit
quantity is extracted from the password file and appended to
the typed password.  The encrypted result  is  required,  as
before, to be the same as the remaining 64 bits in the pass-
word file.  This modification does not increase the task  of
finding  any individual password, starting from scratch, but
now the work of testing a given character string  against  a
large  collection of encrypted passwords has been multiplied
by 4096 ($2 sup 12$).  The reason for this is that there are
4096 encrypted versions of each password and one of them has
been picked more or less at random by the system.

     With this modification, it is likely that the  bad  guy
can spend days of computer time trying to find a password on
a system with hundreds of passwords, and find none  at  all.
More  important  is  the fact that it becomes impractical to
prepare  an  encrypted  dictionary  in  advance.   Such   an
encrypted dictionary could be used to crack new passwords in
milliseconds when they appear.

     There is a (not inadvertent) side effect of this modif-
ication.  It becomes nearly impossible to find out whether a
person with passwords on two or more systems  has  used  the
same password on all of them, unless you already know that.










                           - 8 -


4.  The Threat of the DES Chip

     Chips to perform the DES encryption are already commer-
cially  available and they are very fast.  The use of such a
chip speeds up the process of password hunting by three ord-
ers  of  magnitude.   To  avert this possibility, one of the
internal tables of the DES  algorithm  (in  particular,  the
so-called  E-table)  is changed in a way that depends on the
12-bit random number.  The E-table is inseparably wired into
the  DES  chip,  so that the commercial chip cannot be used.
Obviously, the bad guy could have his own chip designed  and
built, but the cost would be unthinkable.

5.  A Subtle Point

     To login successfully on the UNIX system, it is  neces-
sary  after  dialing  in to type a valid user name, and then
the correct password for that user name.  It is poor  design
to  write  the  login command in such a way that it tells an
interloper when he has typed in a invalid  user  name.   The
response  to an invalid name should be identical to that for
a valid name.

     When the slow encryption  algorithm  was  first  imple-
mented,  the  encryption  was done only if the user name was
valid, because otherwise there was no encrypted password  to
compare with the supplied password.  The result was that the
response was delayed by about one-half second  if  the  name
was  valid, but was immediate if invalid.  The bad guy could
find out whether a particular user name was valid.  The rou-
tine was modified to do the encryption in either case.

CONCLUSIONS

     On the issue of password  security,  UNIX  is  probably
better  than  most  systems.  The use of encrypted passwords
appears reasonably secure in the absence of  serious  atten-
tion of experts in the field.

     It is also  worth  some  effort  to  conceal  even  the
encrypted passwords.  Some UNIX systems have instituted what
is called an ``external security code'' that must  be  typed
when  dialing  into  the  system, but before logging in.  If
this code is changed periodically, then someone with an  old
password will likely be prevented from using it.

     Whenever any  security  procedure  is  instituted  that
attempts  to deny access to unauthorized persons, it is wise
to  keep  a  record  of  both  successful  and  unsuccessful
attempts  to  get  at the secured resource.  Just as an out-
of-hours visitor to a computer center normally must not only
identify  himself,  but a record is usually also kept of his
entry.  Just so, it is a wise precaution to make and keep  a
record  of  all  attempts  to log into a remote-access time-









                           - 9 -


sharing system, and certainly all unsuccessful attempts.

     Bad guys fall on a spectrum whose one  end  is  someone
with  ordinary  access to a system and whose goal is to find
out a particular password (usually that of  the  super-user)
and, at the other end, someone who wishes to collect as much
password information as possible from  as  many  systems  as
possible.   Most  of  the work reported here serves to frus-
trate the latter type; our  experience  indicates  that  the
former type of bad guy never was very successful.

     We recognize that a time-sharing system must operate in
a hostile environment.  We did not attempt to hide the secu-
rity aspects of the operating system,  thereby  playing  the
customary  make-believe game in which weaknesses of the sys-
tem are not discussed no matter  how  apparent.   Rather  we
advertised  the password algorithm and invited attack in the
belief that this approach  would  minimize  future  trouble.
The approach has been successful.

References

[1]  Ritchie, D.M. and Thompson, K.  The  UNIX  Time-Sharing
     System.  Comm. ACM 17 (July 1974), pp. 365-375.

[2]  Proposed Federal Information Processing Data Encryption
     Standard.  Federal Register (40FR12134), March 17, 1975

[3]  Wilkes, M. V.  Time-Sharing Computer Systems.  American
     Elsevier, New York, (1968).

[4]  U. S. Patent Number 2,089,603.